GENERAL
Switching systems such as the telephone switching network are generally designed to interconnect, upon request, selected pairs of customer terminals from a large plurality of terminals connected to the system. The simplest connecting network capable of such interconnections is a single switching matrix designed to connect any idle customer terminal to any other idle terminal in the network, regardless of whether all other terminals in the network are interconnected therein.
To achieve this capability with a single switching matrix it is necessary to employ a number of elemental switches, or crosspoints, within the matrix which increases as the square of the number of customer terminals served by the network. This may result in matrices having prohibitively large numbers of crosspoints.
Fortunately it is not necessary to employ such a capable switching network because advantage can be taken of the theory of trunking probability which recognizes that seldom are more than 10 percent of the terminals active at any particular time. In view of this theory of trunking probability, it is possible, and economically advantageous, to use a less capable switching network.
One such less capable switching arrangement is realized with a multistage connecting network which comprises an ordered plurality of s interconnected stages (v.sub.i). In such a multistage network, each stage v.sub.i includes a plurality of switches v.sub.il, v.sub.i2, . . . v.sub.ir.sbsb.i having input and output links. The input links of each switch in a stage are respectively connected to the output links of switches in the preceding stage while the output links of each switch in a stage are respectively connected to input links of switches in the succeeding stage. The input links of the first stage switches are connected to customer terminals termed input terminals, and the output links of the last stage switches are connected to customer terminals termed output terminals. For purposes of the instant specification, it is assumed that each first stage switch v.sub.lj has n input links, that each last stage switch v.sub.sj has n output links, that there are n input switches (r.sub.l = n) and that there are n output switches (r.sub. s = n). Additionally, only a three-stage network (s = 3) is described herein, although it is to be understood that the disclosed invention is applicable to any value of s.
The words "input" and "output" of phrases "input terminals" and "output terminals" refer, of course, to the arbitrary input and output designations of the switching network. Each "input" or "output" terminal can in fact be the calling or the called party of an interconnection request. In a telephone system, for example, the input terminals may be the telephones of one central office while the output terminals may be the telephones of another central office.
As implied above, it is possible for a customer terminal connected to a multistage switching network to occasionally be blocked from being connected as desired because the network happens to be interconnected in a manner that prevents effecting the desired interconnection. This, of course, is an undesirable situation which, in an appropriately designed network, can be remedied by dismantling existing interconnections and by rearranging the interconnection paths to accommodate the new request. When such a rearrangement is possible, it is said that the new assignment, which is the new set of interconnections desired to be established, is realizable. A switching network which can realize all possible assignments without rearranging existing connections is said to be nonblocking, while a network which can realize all possible assignments only by occasionally rearranging existing connections is said to be merely rearrangeable.
A network is said to be one-sided rearrangeable if it can realize all assignments which interconnect input terminals to all other input terminals, input terminals to output terminals and vice versa, and output terminals to all other output terminals.
A network is said to be two-sided rearrangeable if input terminals can only connect to output terminals (and vice versa).
A network is said to be input-mixed rearrangeable if the input terminals can connect to other input terminals or to output terminals, but output terminals cannot connect to other output terminals. Similarly, a network is said to be output-mixed rearrangeable if output terminals can connect to other output terminals or to input terminals, but input terminals cannot connect to other input terminals.
The above definitions of one-sided rearrangeability, two-sided rearrangeability, input-mixed rearrangeability and output-mixed rearrangeability can be applied to a switch v.sub.ij in the same manner as applied to a network.